<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <meta http-equiv="Content-Style-Type" content="text/css" />
  <meta name="generator" content="pandoc" />
  <title></title>
  <style type="text/css">code{white-space: pre;}</style>
  <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script>
</head>
<body>
<p>stanford大学的算法课程，这是第二学期，比之前的课程的内容更加深入。</p>
<h2 id="图基础">图基础</h2>
<p>第一课是图相关的基础，包括有向图与无向图。同时对图的两种遍历方式，拓扑排序进行了 介绍，同时涉及到了连通分支的概念。这里对拓扑排序和连通分支作简要的笔记。</p>
<h4 id="拓扑排序">拓扑排序</h4>
<p>拓扑排序要求图为DAG（即有向无环图），执行DFS，并以相反的顺序返回后序，可以通过维 护一个栈达到要求。</p>
<p>代码如下图：</p>
<div class="figure">
<img src="figure/dfs_topo.jpg" />
</div>
<p>考虑任何一条边<span class="math">\(v\to{}w\)</span>，在调用<code>dfs(v)</code>的时候，会发生两种状态，即<code>dfs(w)</code>已被调 用并返回或者<code>dfs(w)</code>还未调用。对于DAG，只有这两种情况会发生，如果<code>dfs(w)</code>已发生 并且未返回，则必然是出现了环。</p>
<p>这里有一个非常有趣的例子，Excel软件中如果第一个元素的计算依赖于第二个元素，第二 个依赖于第三个，第三个依赖于第一个，显然就会构成一个环，是无法计算的。</p>
<h4 id="有向图的强连通分支">有向图的强连通分支</h4>
<p>定义：如果顶点<span class="math">\(v\)</span>和顶点<span class="math">\(w\)</span>之间相互有路径，那么它们就是强连通的。</p>
<p>强连通是一个等价关系，因此可以把一个有向图按照强连通关系划分为多个等价类，即强连 通分支。根据这个定义，DAG的强连通分支为顶点的个数。</p>
<p>计算一个无向图的连通分支只需要调用DFS即可实现，但对于有向图的强连通分支，则不易 设计其算法。Tarjan et al.在1972年的论文中提出了一个线性的DFS方法实现强连通分支的 计算，但其实现难度比较大；相比而言，Kosaraju-Sharir在1980年代提出的两步线性方法 则是一个比较容易实现的方法。Gabow等人进一步提出更简单的线性方法。</p>
<p>Kosaraju-Sharir计算强连通分支的算法如下（复杂度为<span class="math">\(O(E+V)\)</span>）：</p>
<ol style="list-style-type: decimal">
<li>先运行对<span class="math">\(G^R\)</span>调用DFS计算后序的反向列表</li>
<li>对原始的图进行DFS遍历，以第1步得到的列表为顺序进行访问，然后每次DFS所经过的结 点属于一个连通分量</li>
</ol>
<p>其证明如下：</p>
<div class="figure">
<img src="figure/kosaraju_proof.jpg" />
</div>
</body>
</html>
